package com.LeeCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 左叶子之和
 */

public class Code404 {
    public static void main(String[] args) {
        Integer[] arr = {1};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code404().sumOfLeftLeaves(root));
    }

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;

        int ans = 0;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
                if (node != null && node.left == null && node.right == null) {
                    ans += node.val;
                }
            }
            node = stack.pop();
            node = node.right;
        }
        return ans;
    }
}
